The present invention relates to circuit design methods for programmable logic arrays, and more particularly to power saving methods for programmable logic arrays.
Programmable logic array (PLA) circuits and gate array (GA) logic circuits are the most common building modules for integrated circuit (IC) logic products. After IC designers describe logic operations by hardware description language (HDL), computer aid design (CAD) tools automatically translate the HDL into PLA or gate array circuits. These two methods (PLA or GA) are exchangeable. Most of logic circuits can be implemented by either way. PLA CAD tools combine all the logic relationships between a large number of input and output signals into one large group of AND operations followed by one large group of OR operations, and represent those operations by arrays of programmable connections. The physical structure of a PLA is highly regular, and its timing is easily predictable. On the contrary, gate array CAD tools break down complex logic calculations into series of single step logic operations such as NAND, NOR, INVERT, and implement those logic operations by a large number of logic gates. Such procedure is called xe2x80x9csynthesizingxe2x80x9d in the art. The physical structures of GA logic circuits are nearly random. That is why they are often called xe2x80x9crandom logic circuitsxe2x80x9d in the art. It usually requires very complex connections between logic gates. As IC fabrication technologies progressed into deep sub-micron, the resistance of conductor lines and the coupling capacitors between conductors became significant. The complex connections in GA logic circuits make timing calibration and performance optimization very difficult even with the helps of the most advanced CAD tools. It is expected that future IC technologies will not be able to improve circuit performance by reducing transistor dimensions due to the resistance and capacitor (RC) of conductor lines. On the other hand, PLA adapts better for the RC problem in advanced IC technologies due to its regular structures. The limitation for PLA comes from its power consumption. PLA consumes much more power than GA. Power requirement makes it nearly impossible to implement a large logic circuit completely by PLA.
Before the invention itself is explained, a typical prior art PLA is first explained to facilitate the understanding of the invention. FIG. 1(a) is a schematic diagram showing the function and geometry of a prior art PLA. This PLA contains two programmable diode arrays (102,103). The first diode array (102) is called the xe2x80x9cAND arrayxe2x80x9d of the PLA because its function is to execute logic AND operations of its inputs. This AND array (102) contains (J+1) pairs of input lines (I0, I0#, I1, I1#, . . . , Ij, Ij#, . . . , IJ, IJ#), and (K+1) output lines (A0, A1, . . . , Ak, . . . , AK), where j, J, k and K are integers. Diodes (100) are selectively connected between the AND array input lines and the AND array output lines to control its logic functions. For the example in FIG. 1(a), A0 is connected to I0, I1#, and IJ# through diodes. If any one of the connected signals (I0, I1#, IJ#) are low, A0 will be low. On the other word, A0=I0*I1#*IJ#, where xe2x80x9c*xe2x80x9d represents logic AND operation. For another example, Ak is connected to I1 and IJ# through diodes so that Ak=[I1*IJ#], . . . etc.
The second diode array (103) of the PLA is called the xe2x80x9cOR arrayxe2x80x9d because its function is to execute logic OR operations. This OR array comprises (K+1) input lines (A0xe2x80x2, A1xe2x80x2, . . . , Akxe2x80x2, . . . , AKxe2x80x2), and (M+1) output lines (R0, R1 . . . , Rm, . . . , RM), where k, K, m and M are integers. Diodes (109) are selectively connected between the OR array input lines and the OR array output lines to control its logic functions. For the example in FIG. 1(a), R0 is connected to A0xe2x80x2, A1xe2x80x2, and Akxe2x80x2 through diodes. If any one of the connected signals (A0xe2x80x2, A1xe2x80x2, Akxe2x80x2) are high, R0 will be high. On the other word, R0=[A0xe2x80x2+A1xe2x80x2+Akxe2x80x2], where xe2x80x9c+xe2x80x9d represents logic OR operation. RM is connected to A1xe2x80x2, Akxe2x80x2 and AKxe2x80x2 through diodes so that RM [A1xe2x80x2+Akxe2x80x2+AKxe2x80x2], . . . etc. The horizontal lines of the AND array and OR array represent intermediate logic terms called xe2x80x9cmintermsxe2x80x9d in the art.
This PLA has (J+1) external input signals (IN1, IN2, . . . , INj, . . . , INJ), where j and J are integers. Each input signal is connected to one PLA input circuitry (105). Details of the PLA input circuitry (105) are shown in FIG. 1(b). For the example, the j""th PLA input signal (INj) is connected to an inverter (121) to generate an inverted signal INj# that is connected to the gate of an n-channel transistor (MN1). The source of MN1 is connected to the drain of another n-channel transistor (MN3). The drain of MN1 is connected to one PLA AND array input signal (Ij), that is also connected to the drain of a p-channel transistor (MP1). The source of MP1 is connected to power supply voltage Vcc. The gate of MP1 is connected to pre-charge signal PG#, that is also connected to the gate of MN3. The source of MN3 is connected to ground. The signal INj# is inverted by an inverter (122) before it is connected to the gate of an n-channel transistor (MN2). The source of MN2 is connected to the drain of another n-channel transistor (MN4). The drain of MN2 is connected to the other PLA AND array input signal (Ij#), that is also connected to the drain of a p-channel transistor (MP2). The source of MP2 is connected to Vcc, while the gate of MP2 is connected to the pre-charge signal PG#. The gate of MN4 is also connected to PG#. The source of MN4 is connected to Vss. When the PLA is idle, PG# is low, and both Ij and Ij# are pulled to power supply voltage Vcc. When the PLA is activated by pulling PG# high, Ij and Ij# are activated; if INj is high, Ij# is driven to ground voltage Vss while Ij is at high impedance state; if INj is low, Ij is driven to Vss while Ij# is at high impedance state. Referring back to FIG. 1(a), paired input signals are connected to vertical input lines (I0, I0#, I1, I1#, . . . , Ij, Ij#, . . . , IJ, IJ#) of the AND array (102). These AND array input lines intersect horizontal AND array output lines (A1, A2, . . . , Ak, . . . , AK). At idle state, these horizontal lines (A1, A2, . . . , Ak, . . . , AK) of the AND array are pre-charged to Vcc using p-channel transistors (104) controlled by pre-charge signal PG#. The signal PG# is also connected to a delay circuit (108) to generate OR array pre-charge signals (PG, PG1#). FIG. 1(c) shows the structures of the delay circuit (108). A programmable delay circuitry (125) provides proper delay time, and the output of the delay circuit is connected to an inverter (126) to generate signal PG that is also connected to another inverter (127) to generate signal PG1#. These OR array pre-charge signals (PG, PG1#) control the data converters (107) between AND array and OR array. The structure of the data converter (107) is shown in FIG. 1(d). The k""th AND array output signal (Ak) is inverted by an inverter (123) before connected to the gate of a p-channel transistor (MP5). The source of MP5 is connected to PG1#, while its drain is connected to corresponding OR array input line (Akxe2x80x2). Signal Akxe2x80x2 is also connected to the drain of an n-channel transistor (MN5). The gate of MN5 is connected to PG, while its source is connected to ground Vss. At idle state, PG1# is low and PG is high so that Akxe2x80x2 is always driven to Vss. When the OR array (103) is activated, PG is low and PG1# is high; Akxe2x80x2 is driven to Vcc if Ak is high, while it is at high impedance if Ak is low.
FIG. 1(e) illustrates the timing waveforms of critical signals for the PLA. Before time Tst, the PLA is at idle state; both PG# and PG1# are low; all the AND array input signals (Ij, Ij#, j=0, 1, . . . , J) and output signals (Ak, k=0, 1, . . . , K) are high; all the OR array input signals (Akxe2x80x2, k=0, 1, . . . , K) and all the PLA output signals (Rm, m=0, 1, . . . , M) are low. At time Tst, the AND arrays are activated by pulling PG# high, and some of the AND array output signals (Ak, k=0, 1, . . . , K) are pulled low depending on the diode connections and the value of PLA input signals. At time Tr in FIG. 1(e), PG1# is pulled high to activate the PLA OR arrays, and the values of the AND array outputs (Ak) propagate to the OR array to generate PLA outputs (Rm). The PLA outputs (Rm) are ready at time Td in FIG. 1(e). To terminate the PLA operation, PG# is pull down at time Trst, and all the signals return to their idle states at time Te as shown in FIG. 1(e).
The above example uses diodes in the programmable arrays. There are many other types of prior art PLA""s. For example, many prior art PLA""s use n-channel metal-oxide-semiconductor (MOS) transistors in the programmable array. The AND-OR arrays can be replaced by NOR-NAND arrays or other types of logic combinations. All of those prior art PLA""s follow similar operational principles, and they have the same problems that can be solved by the same solutions of the present invention. We will not describe other prior art PLA""s in further details.
For simplicity, we only reveal small parts of the programmable connections in the AND arrays and OR arrays in FIG. 1(a). In reality, a PLA usually have hundreds of minterms. FIG. 1(f) shows a symbolic representation used by the present inventor to show the connections in large programmable arrays. Each vertical line in the AND array (161) represents a pair of input lines. Each horizontal line in the AND array (161) represents one output line. An open dot (164) at the intersection between an input line and an output line of the AND array (161) represents a programmable connection between a positive input line and an output line at the intersection. A solid dot (163) at the intersection between an input line and an output line of the AND array (161) represents a programmable connection between a negative input line and an output line at the intersection. Each horizontal line in the OR array (162) represents an OR array input line. Each vertical line in the OR array (162) represents one output line of the OR array. An open dot (165) at the intersection between an input line and an output line of the OR array (162) represents a programmable connection. The peripheral circuits are not shown in details in this symbolic diagram. The symbolic diagram in FIG. 1(f) allows us to show the connections of large PLA with simple diagrams. We will use similar symbolic diagrams in the following discussions.
PLA circuits usually use smaller areas than combination logic circuits of the same functions. The regular structures of PLA also make it much easier to make modifications. Timing and speed of PLA circuits are much easier to control, especially for advanced IC technologies. Power consumption is its major disadvantage. The above example in FIGS. 1(a-f) illustrates the reasons why prior art PLA""s consume more power than gate array logic circuits. Gate array logic circuits break down complex logic calculations into single step logic operations, and implement those logic operations by series of logic gates. During a logic calculation, only those gates change their outputs would consume power. For most of cases, only a small part of the gates in a large GA logic circuitry consume power. A PLA combines all the logic relations between a large number of input signals and output signals into programmable logic arrays with hundreds of minterms. A PLA always consumes power whenever it is activated. Even for the simplest logic operations the PLA will consume maximum power as if all the inputs and outputs are involved. Therefore, PLA""s usually consume much more power than equivalent GA circuits.
Engeler et al. in U.S. Pat. No. 4,782,249 provided a method to reduce PLA power consumption by designing PLA using CMOS static circuits. A static PLA consumes no power when all the PLA inputs are not changed. However, the static PLA still consumes a lot of power because each PLA signal is connected to a large loading. The static PLA also occupies much larger area than conventional PLA. The invention provides partial solution to the power consumption problem, but the major sources of the problem are not solved.
The primary objective of this invention is, therefore, to providing practical methods to reduce power consumed by PLA circuits. Another objective of this invention is to improve the performance of PLA. The other objective of the present invention is to provide power saving and performance improvement without increasing area and cost of PLA. Another primary objective of the present invention is to provide the capability to maximize the performance of logic circuits using advanced IC fabrication technologies.
These and other objectives are accomplished by novel PLA optimization methods. A large PLA is partitioned into smaller sub-PLA""s. Minterms with shared logic terms are grouped together into the same partitions. Each individual PLA sub-array is activated only when its operation is required. There will be no power consumption whenever a sub-array won""t influence the final outputs. A PLA of the present invention has the regular structures of prior art PLA""s, while it has the power consumption characteristics of current art GA logic circuits. The power consumption of the resulting PLA is as low as equivalent GA logic circuits. For most cases, PLA""s of the present invention occupy smaller areas than prior art PLA""s. The performance is also improved.
While the novel features of the invention are set forth with particularly in the appended claims, the invention, both as to organization and content, will be better understood and appreciated, along with other objects and features thereof, from the following detailed description taken in conjunction with the drawings.